// 最短路径
#ifndef SHORT_PATH_H
#define SHORT_PATH_H

#include "../model/mgraph.h"

/**
 * 求某一点到所有点的最短路径-迪杰斯特拉算法
 * @param graph 传入图
 * @param v 传入起点的下标
 * @param pathArc 传入用于储存起点到终点的最短路径中终点的前驱，例如pathArc[2]=1表示v到索引为2的点的最短路径的前驱是索引为1的点
 * @param shortTable 传入用于储存起点到各点的权值和的数组，例如shortTable[3]=10表示v到索引为3的点的最短路径长度为10
 */
void dijkstra(MGraph &, int, int *, int *);

/**
 * 求所有点到每一个点的最短路径-弗洛伊德算法
 * @param graph 传入图
 * @param pathArc 用于储存每个点最短路径前驱的二维数组，例如pathArc[1][3]=2表示索引为1的顶点到索引为3的顶点的最短路径中，终点3的前驱是索引为2的顶点
 * @param shortTable 用于储存顶点到顶点最短路径的权值和的二维数组，这个二维数组一开始时就是图的邻接矩阵，例如shortTable[1][3]=6表示索引为1的顶点到索引为3的顶点最短路径权值和为6
 */
void floyd(MGraph &, int **, int **);

#include "./shortest-path.cpp"

#endif